# -*- coding: utf-8 -*-

"""
    Time    : 2020/12/2 下午4:11
    Author  : Thinkgamer
    File    : 010-正则表达式匹配.py
    Software: PyCharm
    Desc    : https://leetcode-cn.com/problems/regular-expression-matching/
"""

"""
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖整个字符串s的，而不是部分字符串。

示例 1：
输入：s = "aa" p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

示例 2:
输入：s = "aa" p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例3：
输入：s = "ab" p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

示例 4：
输入：s = "aab" p = "c*a*b"
输出：true
解释：因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 5：
输入：s = "mississippi" p = "mis*is*p*."
输出：false

提示：
0 <= s.length <= 20
0 <= p.length <= 30
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
保证每次出现字符 * 时，前面都匹配到有效的字符
"""


# 穷举进行判断，太容易出错了，放弃这种思路
def is_match_failed(s, p):
	i = 0
	j = 0
	if p[-2:] == ".*":
		return True
	while i < len(s) and j < len(p):
		# 如果对应位相等， 分三种情况：字符相等，p[j] = "."，p[j] = "*"
		if s[i] == p[j] or p[j] == "." or p[j] == "*":
			if s[i] == p[j] or p[j] == ".":
				i += 1
				j += 1
			# p[j] == "*"
			else:
				# 要判断 i 是否走到终点
				if i == len(s) - 1 and j != len(p) - 1:
					if j != len(p) - 1:
						j += 1
					else:
						if p[j-1] == s[i]:
							i += 1
							j += 1
						else:
							return False
				else:
					if p[j-1] == s[i] or p[i-1] == "." or (j + 1 < len(p) and p[j+1] == s[i]):
						i += 1
						j += 1
					else:
						return False
		# 如果对应位不等
		else:
			j += 1
			if j < len(p) and p[j] == "*":
				j += 1
			else:
				return False
	
	if i == len(s) and j == len(p):
		return True
	else:
		return False


# 参考题解，使用动态规划的思路
# https://leetcode-cn.com/problems/regular-expression-matching/solution/zheng-ze-biao-da-shi-pi-pei-by-leetcode-solution/
def is_match(s, p):
	
	pass

for s, p in [
	["aa", "a"],   # False
	["aa", "a*"],  # True
	["ab", ".*"],  # True
	["aab", "c*a*b"],  # True
	["mississippi", "mis*is*p*."],  # False
	["aaa", "ab*a"],  # False
	["aaa", "ab*a*c*a"],  # True
	["ab", ".*c"],  # False
	["aaa", ".*"],  # True
	["a", "ab*"],   # True
]:
	result = is_match(s, p)
	print(result)

